/**
 * 算法
 */
///////////////////////////////////////////////////算法 start//////////////////////////////////////////////////
/////////////////////////////////////////二分法 start////////////////////////////////////////////
/**
 * 相关题
 * 704.二分查找（简单）
 * 34.在排序数组中查找元素的第一个和最后一个位置（中等）
 */
{
  // 套路模板
  /**
   * 
  function binarySearch(nums, target) {
    let left = 0, right = ...;
    while (...) {
      let mid = parseInt(left + (right - left) / 2);
      if (nums[mid] == target) {
          ...;
      } else if (nums[mid] < target) {
          left = ...;
      } else if (nums[mid] > target) {
          right = ...;
      }
    }
    return ...;
  }
  */

  // 查找一个数
  function binarySearch(nums, target) {
    let left = 0, right = nums.length - 1;
    // while (left < right) {
    while (left <= right) {
      let mid = parseInt(left + (right - left) / 2);
      if (nums[mid] == target) {
          return mid;
      } else if (nums[mid] < target) {
          left = mid + 1;
      } else if (nums[mid] > target) {
          right = mid - 1;
      }
    }
    return -1;
    // return nums[left] == target ? left : -1;
  }
  /**
   * 
   *  因为我们初始化 right = nums.length - 1
      所以决定了我们的「搜索区间」是 [left, right]
      所以决定了 while (left <= right)
      同时也决定了 left = mid+1 和 right = mid-1

      因为我们只需找到一个 target 的索引即可
      所以当 nums[mid] == target 时可以立即返回
   */
  const nums = [-1,0,3,5,9,12], target = 9;
  console.log(binarySearch(nums, target));
  // 如果while使用left < right ,需要打个补丁  return nums[left] == target ? left : -1;


  // 如果是搜索[1,2,2,2,3]， target为2
  // 左侧查找
  function leftBound(nums, target) {
    let left = 0, right = nums.length - 1;
    while (left <= right) {
      let mid = parseInt(left + (right - left) / 2);
      if (nums[mid] == target) {
        right = mid - 1;
      } else if (nums[mid] < target) {
        left = mid + 1;
      } else if (nums[mid] > target) {
        right = mid - 1;
      }
    }
    // return left;  // 返回right也可以
    // return nums[left] == target ? left : -1;

    if (left >= nums.length || nums[left] != target)
      return -1;
    return left;
  }
  /**
   *  因为我们初始化 right = nums.length
      所以决定了我们的「搜索区间」是 [left, right)
      所以决定了 while (left < right)
      同时也决定了 left = mid + 1 和 right = mid

      因为我们需找到 target 的最左侧索引
      所以当 nums[mid] == target 时不要立即返回
      而要收紧右侧边界以锁定左侧边界
   */
  //这个算法其实算的是target个数，如果要返回index或-1，则return nums[left] == target ? left : -1;
  const nums2 = [1,2,2,2,3], target2 = 2;
  console.log(leftBound(nums2, target2))

  // 右侧查找
  function rightBound(nums, target) {
    let left = 0, right = nums.length - 1;
    while (left <= right) {
      let mid = parseInt(left + (right - left) / 2);
      if (nums[mid] == target) {
        left = mid + 1;
      } else if (nums[mid] < target) {
        left = mid + 1;
      } else if (nums[mid] > target) {
        right = mid - 1;
      }
    }
    // return left;  // 返回right也可以
    // return nums[left] == target ? left : -1;

    if (right < 0 || nums[right] != target)
      return -1;
    return right;
  }
  /**
   *  因为我们初始化 right = nums.length
      所以决定了我们的「搜索区间」是 [left, right)
      所以决定了 while (left < right)
      同时也决定了 left = mid + 1 和 right = mid

      因为我们需找到 target 的最右侧索引
      所以当 nums[mid] == target 时不要立即返回
      而要收紧左侧边界以锁定右侧边界

      又因为收紧左侧边界时必须 left = mid + 1
      所以最后无论返回 left 还是 right，必须减一
   */
  const nums3 = [1,2,2,2,3], target3 = 2;
  console.log(rightBound(nums3, target3))

  /**
   * 前提条件：有序数组
   * 总结：二分法查找分三种：1.查找一个数；2.左侧查找；3.右侧查找
   * 方法：统一使用闭区间，即[left, right], right=nums.length - 1,while(left<=right);
   * 注意点：防止边界溢出，左侧查找需做判断left >= nums.length || nums[left] != target，右侧查找需做判断right < 0 || nums[right] != target
   * 其他方法： 左闭又开，即[left,right),right = nums.length,while(left < right);
   */
}
/////////////////////////////////////////二分法 end////////////////////////////////////////////
/////////////////////////////////////////滑动窗口 start////////////////////////////////////////////
{
  /**
   * 76.最小覆盖子串（困难）
    567.字符串的排列（中等）
    438.找到字符串中所有字母异位词（中等）
    3.无重复字符的最长子串（中等）
   */
  // 3.无重复字符的最长子串（中等）
  function lengthOfLongestSubstring(s) {
    let win = {};
    let left = 0, right = 0;
    let res = 0; // 记录结果

    while (right < s.length) {
        let c = s[right];

        right++;
        // 进行窗口内数据的一系列更新
        if (!win[c]) {
          win[c] = 1;
        } else {
          win[c]++;
        }
        // 判断左侧窗口是否要收缩
        while (win[c] > 1) {
          let d = s[left];

          left++;
          // 进行窗口内数据的一系列更新
          win[d]--;
        }

        // 在这里更新答案
        res = Math.max(res, right - left);
    }

    return res;
  }
  const s2 = "abcabcdb";
  console.log(lengthOfLongestSubstring(s2));

  //  567.字符串的排列（中等）
  function checkInclusion(t, s) {
    let win = {}, need = {};
    for(let c of t) {
      if (!need[c]) {
        need[c] = 1;
      } else {
        need[c]++;
      }
    }

    let left = 0, right = 0;
    let valid = 0;
    while(right < s.length){
      let c = s[right];
      right++;

      if (need[c]) {
        if (!win[c]) {
          win[c] = 1;
        } else {
          win[c]++;
        }
        if (win[c] == need[c])
            valid++;
      }
      // console.log(valid, need, win);
      //因为此题求的布尔值，可能有多种情况，所以只要是有一种情况存在就行可，这里使用大于等于，尽可能的寻找，然后直接return
      while(right - left >= t.length) {  
        // 非框架逻辑，细节判断，
        if (valid == Object.keys(need).length)
          return true;
        let d = s[left];
        left++;
        
        if (need[d]) {
          // 此判断好像没用
          if (win[d] == need[d]){
            valid--;
          }
          win[d]--;
        }
      }
    }
    return false;
  }
  const s3 = "dia", s4 = "edidabbbooo";
  console.log(checkInclusion(s3, s4));

  // 76.最小覆盖子串（困难）
  function minWindow(t, s){
    let win = {}, need = {};
    for(let c of t) {
      if (!need[c]) {
        need[c] = 1;
      } else {
        need[c]++;
      }
    }

    let left = 0, right = 0;
    let valid = 0;
    let start = 0;
    while(right < s.length){
      let c = s[right];
      right++;

      if (need[c]) {
        if (!win[c]) {
          win[c] = 1;
        } else {
          win[c]++;
        }
        if (win[c] == need[c])
            valid++;
      }
      // console.log(valid, need, win);
      while(valid == t.length) {  //因为此题求的是最小子串，需要算出start，所以只能是等于的情况
        // 非框架逻辑，细节判断，
        // if (right - left < max) {
          start = left;
          len = right - left;
        // }
        
        let d = s[left];
        left++;
        
        if (need[d]) {
          // console.log(d, valid, need, win);
          if (win[d] == need[d]){
            valid--;
          }
          win[d]--;
        }
      }
    }
    return s.substr(start, len);
  }
  const s5 = "ADOBECODEBANC", t6 = "ABC";
  console.log(minWindow(t6, s5));

  // 438.找到字符串中所有字母异位词（中等）
  function findAnagrams(t, s) {
    let need = {}, win = {};
    for(let c of t) {
      if (!need[c]) {
        need[c] = 1;
      } else {
        need[c]++;
      }
    }

    let left = 0, right = 0;
    let valid = 0;
    let res = [];
    while (right < s.length) {
      let c = s[right];
      right++;

      if (need[c]){
        if (!win[c]){
          win[c] = 1;
        } else {
          win[c]++;
        }
        if (win[c] == need[c]) {
          valid++;
        }
      } 

      //因为此题求的多种结果，可能有多种情况，这里使用大于等于，尽可能的寻找，然后将结果搜集起来
      while(right - left >= t.length) {
        // 非框架逻辑，细节判断，
        if (valid == Object.keys(need).length){
          res.push(left);
        }

        let d = s[left];
        left++;
        if (need[d]) {
          if(win[d] == need[d]) {
            valid--;
          }
          win[d]--;
        }
      }
    }
    return res;
  }
  const s7 = "cbaebabacd", p8 = "abc";
  console.log(findAnagrams(p8,s7));

  /**
   * 滑动窗口方法总结：
   * 需要两个指针left，right，还需要一个win窗口，object类型，用于基数窗口内已经计算出的字符个数，
   * need用于一开始计算出子串各个字符的个数，如abbc，转为need为{a:1,b:2,c:1},
   * valid用于计算win中已经存在的需要的字符且数量相等的计算，只有该字符存在于win中且数量相同，valid才会加1
   * 两个while用于left和right加1计算，先计算right，后计算left
   * 主要逻辑：
   * 判断当前指针走的字符存不存在与need当中，如果存在，就将该字符存于win当中且计算数量，当win当中的数量和need当中的数量相同时，valid加1，
   * 再通过while条件判断，开始计算窗口是否需要缩小，缩小时，将左侧的字符再次进行计算，判断是否在need当中，
   * 如果在其中，判断一下和win当中的字符出现次数是否相同，如果相同，valid就减去1，完了之后，窗口相应的字符计数也减去1，至此整个框架逻辑结束
   * 
   * 注意： valid和need有时候并不需要，如直接求出不同字符的时候，need里面的基数永远是1，所以valid和need省略即可，直接计算出结果，看 3.无重复字符的最长子串（中等）
   */
}
/////////////////////////////////////////滑动窗口 end////////////////////////////////////////////
/////////////////////////////////////////回溯 start////////////////////////////////////////////
{
  // 全排列
  var permute = function(nums) {
    const res = [], path = [];
    
    function backtracking(n, k, used) {
        if(path.length === k) {
            res.push(Array.from(path));
            return;
        }
        for (let i = 0; i < k; i++ ) {
            if(used[i]) continue;
            path.push(n[i]);
            used[i] = true; 
            backtracking(n, k, used);
            // console.log(used, path, 'path')
            path.pop();
            used[i] = false;
        }
    }
    backtracking(nums, nums.length, []);
    return res;
  };
  console.log(permute([1,2,3]))

  // N皇后
  var solveNQueens = function(n) {
    function isValid(row, col, chessBoard, n) {

        for(let i = 0; i < row; i++) {
            if(chessBoard[i][col] === 'Q') {
                return false
            }
        }

        for(let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if(chessBoard[i][j] === 'Q') {
                return false
            }
        }

        for(let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if(chessBoard[i][j] === 'Q') {
                return false
            }
        }
        return true
    }

    function transformChessBoard(chessBoard) {
        let chessBoardBack = []
        chessBoard.forEach(row => {
            let rowStr = ''
            row.forEach(value => {
                rowStr += value
            })
            chessBoardBack.push(rowStr)
        })

        return chessBoardBack
    }

    let result = []
    function backtracing(row,chessBoard) {
        if(row === n) {
            result.push(transformChessBoard(chessBoard))
            return
        }
        for(let col = 0; col < n; col++) {
            if(isValid(row, col, chessBoard, n)) {
                chessBoard[row][col] = 'Q'
                backtracing(row + 1,chessBoard)
                chessBoard[row][col] = '.'
            }
        }
    }
    let chessBoard = new Array(n).fill([]).map(() => new Array(n).fill('.'))
    backtracing(0,chessBoard)
    return result;
  };
  const n = 4;
  console.log(solveNQueens(n));

  // 组合
  function combine(n, k) {
    let res = [];
    let path = [];
    function backtracing(n, k, start) {
      for(let i = start; i < n - (k - path.length) + 1; i ++) {
        if (path.length == k) {
          res.push([...path]);
          return;
        }
        path.push(i);
        backtracing(n, k, i + 1);
        path.pop();
      }
    }
    backtracing(n, k ,0);
    return res;
  }
  console.log(combine(4, 2));
  /**
   * 回溯总结：
   * 常用场景：组合、排列、切割、子集、棋盘，纯属暴力解法，可通过剪枝方式进行优化
   * 思路：递归
   * 需要变量：res，搜集最终结果；path，搜集路径结果，
   * 常用套路：使用递归依次众向向下查找路径，横向通过for循环，
   * 套路模板：
   * function backtracking(参数) {
   *    let res = [], path = [];
        if (终止条件) {
            存放结果;
            return;
        }

        for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
            处理节点;
            backtracking(路径，选择列表); // 递归
            回溯，撤销处理结果
        }
        return res;
    }
   */
}
/////////////////////////////////////////回溯 end////////////////////////////////////////////
/////////////////////////////////////////BFS start//////////////////////////////////////////
{

}
/////////////////////////////////////////BFS end////////////////////////////////////////////
/////////////////////////////////////////链表 start//////////////////////////////////////////
{
  // 合并两个有序列表
  // 21.合并两个有序链表（简单）
  function ListNode(val, next) {
    this.val = (val === undefined ? 0 : val)
    this.next = (next === undefined ? null : next)
  }
  function mergeTwoLists (l1, l2) {
    const prehead = new ListNode(-1);
    let prev = {val: -1, next: null};
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            prev.next = l1;
            l1 = l1.next;
        } else {
            prev.next = l2;
            l2 = l2.next;
        }
        prev = prev.next;
    }

    // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
    prev.next = l1 === null ? l2 : l1;

    return prehead.next;
  }
  const l1 = {val: 1,next: {val: 2, next: {val: 4, next: null}}}, l2 = {val: 1,next: {val: 3, next: {val: 4, next: null}}};
  console.log(mergeTwoLists(l1, l2), 999);
  // 检查是否有环
  // 141.环形链表（简单）
  // 明明是两个参数，head怎么传？
  // head = [3,2,0,-4], pos = 1
  var hasCycle = function(head) {
    // 快慢指针初始化指向 head
    let slow = head;
    let fast = head;
    // 快指针走到末尾时停止
    while (fast && fast.next) {
      // 慢指针走一步，快指针走两步
      slow = slow.next;
      fast = fast.next.next;
      // 快慢指针相遇，说明含有环
      if (slow == fast) {
        return true;
      }
    }
    // 不包含环
    return false;
  };

  // 获取两个链表的交点
  // 160.相交链表（简单）
  var getIntersectionNode = function(headA, headB) {
    // p1 指向 A 链表头结点，p2 指向 B 链表头结点
    let p1 = headA, p2 = headB;
    while (p1 != p2) {
        // p1 走一步，如果走到 A 链表末尾，转到 B 链表
        if (p1 == null) p1 = headB;
        else            p1 = p1.next;
        // p2 走一步，如果走到 B 链表末尾，转到 A 链表
        if (p2 == null) p2 = headA;
        else            p2 = p2.next;
    }
    return p1;
  };

  // 获取链表的中间点
  // 876.链表的中间结点（简单）
  var middleNode = function(head) {
    // 快慢指针初始化指向 head
    let slow = head, fast = head;
    // 快指针走到末尾时停止
    while (fast != null && fast.next != null) {
        // 慢指针走一步，快指针走两步
        slow = slow.next;
        fast = fast.next.next;
    }
    // 慢指针指向中点
    return slow;
  };
  /**
   * 总结：思想好理解，但是js怎么调试？
   * 链表也属于双指针范围
   */
  /**
   * 其他题
   * 142.环形链表 II（中等）
   * 19.删除链表的倒数第 N 个结点（中等）
   * 23.合并K个升序链表（困难）
   */
}
/////////////////////////////////////////链表 end////////////////////////////////////////////
/////////////////////////////////////////双指针 start//////////////////////////////////////////
{
  /**
   * 数组问题，链表问题
   */
  // nsum问题
  // 两数之和，正常版
  function twoSum(nums, target) {
    nums = nums.sort((a, b) => a - b);
    let left = 0, right = nums.length - 1;
    let res = [];
    while(left < right) {
      let sum = nums[left] + nums[right];
      if (sum < target) {
        left++;
      } else if (sum > target) {
        right--;
      } else {
        return [left, right]
      }
    }
    return res;
  }
  const n1 = [2,7,11,15], target1 = 9;
  console.log(twoSum(n1, target1));

  // 三数之和 正常版
  function twoSum4(nums, target, start = 0) {
    let left = start, right = nums.length - 1;
    while(left < right) {
      let sum = nums[left] + nums[right];
      if (sum < target) {
        left++;
      } else if (sum > target) {
        right--;
      } else {
        return [nums[left], nums[right]];
      }
    }
    return [];
  }

  function threeSum2 (nums, target) {
    nums = nums.sort((a, b) => a - b);
    let res = [];
    let n = nums.length;
    for(let i = 0; i < n; i++) {
      let triple = twoSum4(nums, target - nums[i], i + 1);
  
      if (triple.length > 0) {
        triple.push(nums[i]);
        res.push(triple);
      }
    }
  
    return res;
  }

  const res1 = [-1,0,1,2,-1,-4], t4 = 0;
  console.log(threeSum2(res1 , t4), 'kkk');

  // 两数之和, 如果有重复的元素，应该做while循环判断，不重复结果
  function twoSum1 (nums, target, start = 0) {
    nums = nums.sort((a, b) => a - b);
    let l = start, r = nums.length - 1;
    let res = [];
    while(l < r) {
      let sum = nums[l] + nums[r];
      let lv = nums[l], rv = nums[r];
      if (sum < target) {
        while(l < r && nums[l] == lv) l++;
      } else if (sum > target) {
        while(l < r && nums[r] == rv) r--;
      } else {
        res.push([nums[l], nums[r]]);
        while(l < r && nums[l] == lv) l++;
        while(l < r && nums[r] == rv) r--;
      }
    }
    return res;
  }
  const n = [1,1,1,2,2,3,3],target = 4;
  console.log(twoSum1(n, target), 'iii');

  // 三数之和
  function twoSum2 (nums, target, start = 0) {
    let l = start, r = nums.length - 1;
    let res = [];
    while(l < r) {
      let sum = nums[l] + nums[r];
      let lv = nums[l], rv = nums[r];
      if (sum < target) {
        while(l < r && nums[l] == lv) l++;
      } else if (sum > target) {
        while(l < r && nums[r] == rv) r--;
      } else {
        res.push([nums[l], nums[r]]);
        while(l < r && nums[l] == lv) l++;
        while(l < r && nums[r] == rv) r--;
      }
    }
    return res;
  }
  function threeSum1 (nums, target) {
    nums = nums.sort((a, b) => a - b);
    let res = [];
    let n = nums.length;
    for(let i = 0; i < n; i++) {
      let triple = twoSum2(nums, target - nums[i] ,i + 1);
      for (let v of triple) {
        v.push(nums[i]);
        res.push(v);
      }
      // 跳过第一个数字重复的情况，否则会出现重复结果
      while (i < n - 1 && nums[i] == nums[i + 1]) i++;
    }
    return res;
  }
  const n2 = [-1, 0, 1, 2, -1, -4], t2 = 0;
  console.log(threeSum1(n2, t2));

  // nSum通解，递归思路,
  function nSumTarget(nums, n, start, target) {
    nums = nums.sort();
    let res = [];
    let sz = nums.length;
    if (n < 2 || sz < n) return res;
    if (n = 2){
      let l = start, r = nums.length - 1;
      while(l < r) {
        let sum = nums[l] + nums[r];
        let lv = nums[l], rv = nums[r];
        if (sum < target) {
          while(l < r && nums[l] == lv) l++;
        } else if (sum > target) {
          while(l < r && nums[r] == rv) r--;
        } else {
          res.push([nums[l], nums[r]]);
          while(l < r && nums[l] == lv) l++;
          while(l < r && nums[r] == rv) r--;
        }
      }
    } else {
      for(let i = start; i < sz; i++) {
        let triple = twoSum2(nums, n - 1, i + 1, target - nums[i]);
        for (let v of triple) {
          v.push(nums[i]);
          res.push(v);
        }
        // 跳过第一个数字重复的情况，否则会出现重复结果
        while (i < sz - 1 && nums[i] == nums[i + 1]) i++;
      }
    }
    return res;
  }

  console.log(threeSum1(n2, t2));

  /**
   * 总结：双指针方法可用于链表和普通数组，通常有left，right指针，或者slow，fast指针，
   * 链表查找next，数组指定index
   */
}
/////////////////////////////////////////双指针 end////////////////////////////////////////////
/////////////////////////////////////////二叉树和BST end////////////////////////////////////////////
{
  /**
    *  226.翻转二叉树（简单）
    *  114.二叉树展开为链表（中等）
    *  116.填充每个节点的下一个右侧节点指针（中等）
   */
  // 前序遍历
   var preorderTraversal = function(root) {
    let res=[];
    const dfs=function(root){
        if(root===null)return ;
        //先序遍历所以从父节点开始
        res.push(root.val);
        //递归左子树
        dfs(root.left);
        //递归右子树
        dfs(root.right);
    }
    //只使用一个参数 使用闭包进行存储结果
    dfs(root);
    return res;
   };
   // 中序遍历
   var inorderTraversal = function(root) {
    let res=[];
    const dfs=function(root){
        if(root===null)return ;
        //递归左子树
        dfs(root.left);
        res.push(root.val);
        //递归右子树
        dfs(root.right);
    }
    //只使用一个参数 使用闭包进行存储结果
    dfs(root);
    return res;
  };
  // 后续遍历
  var postorderTraversal = function(root) {
    let res=[];
    const dfs=function(root){
        if(root===null){
            return ;
        }
        dfs(root.left);
        dfs(root.right);
        res.push(root.val);
    }
    dfs(root);
    return res;
  };
  // 226.翻转二叉树（简单）
  function invertTree (root) {
    if (!root){
      return null;
    }

    let tmp = root.left;
    root.left = root.right;
    root.right = tmp;
    invertTree(root.left);
    invertTree(root.right);
    return root;
  }
  // 226.翻转二叉树（简单）
  function connect(root) {
    if (!root){
      return null;
    }
    connectTwoNode(root.left, root.right);
    return root;
  }

  // 116.填充每个节点的下一个右侧节点指针（中等）
  function connectTwoNode(node1, node2) {
    if (!node1 || !node2) return null;
    node1.next = node2;
    connectTwoNode(node1.left, node1.right);
    connectTwoNode(node2.left, node2.right);
    connectTwoNode(node1.right, node2.left);
  }

  // 114.二叉树展开为链表（中等）
  function flatten(root) {
    if (!root) return null;
    flatten(root.left);
    flatten(root.right);

    let left = root.left;
    let right = root.right;
    
    root.left = null;
    root.right = left;

    let p = root;
    while(p.right != null) {
      p = p.right;
    }
    p.right = right;
  }
  // 654.最大二叉树（中等） 不对？
  function constructMaximumBinaryTree(nums) {
    return build(nums, 0, nums.length - 1);
  }
  function build (nums, start, end) {
    if(start > end) return null;
    let maxVal = 0;
    let index = -1;
    for(let i = start; i <= end; i++) {
        if(nums[i] > maxVal) {
            index = i;
            maxVal = nums[i];
        }
    }

    let root = new TreeNode(maxVal);
    root.left = build(nums, start, index - 1);
    root.right = build(nums, index + 1, end);

    return root;
  }
  // 寻找第K小的数
  function kthSmallest(root, k) {
    let res = 0, rank = 0;
    function traverse(root, k) {
        if (!root) return null;
        traverse(root.left, k);
        rank++;
        if (k == rank) {
        res = root.val;
        return;
        }
        traverse(root.right, k);
    }
    traverse(root, k);
    return res;
  }

  // 538. 把二叉搜索树转换为累加树
  var convertBST = function(root) {
    let sum = 0;
    traverse(root);
    function traverse(root) {
        if(!root) return null;
        traverse(root.right);
        sum += root.val;
        root.val = sum;
        traverse(root.left);
    }
    return root;
  };
  /**
   * 
   * 二叉树查找思想，主要是递归，递归左右节点，然后做相应处理
   */
  /**
   *  BST：左边小，右边大
   *  450.删除二叉搜索树中的节点（中等）
      701.二叉搜索树中的插入操作（中等）
      700.二叉搜索树中的搜索（简单）
      98.验证二叉搜索树（中等）
   */
  // 验证是否是BST
  function isValidBST(root) {
    return isValidBSTNodes(root, null, null);
  }

  /* 限定以 root 为根的子树节点必须满足 max.val > root.val > min.val */
  function isValidBSTNodes(root, min, max) {
      // base case
      if (root == null) return true;
      // 若 root.val 不符合 max 和 min 的限制，说明不是合法 BST
      if (min != null && root.val <= min.val) return false;
      if (max != null && root.val >= max.val) return false;
      // 限定左子树的最大值是 root.val，右子树的最小值是 root.val
      return isValidBSTNodes(root.left, min, root) 
          && isValidBSTNodes(root.right, root, max);
  }
  // 700 二叉搜索树中的搜索(具有BST特性)
  // 方法一，普通搜索
  function searchBST(root, target) {
    if(!root) return null;
    if(root.val == target) return root;
    let left = searchBST(root.left, target);
    let right = searchBST(root.right, target);
    return !left ? right : left;
  }
  // 方法二,二分法的思想
  function searchBST(root, target) {
    if(!root) return null;
    if (root.val > target) {
      return searchBST(root.left, target);
    }
    if (root.val < target) {
      return searchBST(root.right, target);
    }

    return root;
  }

  // 450.删除二叉搜索树中的节点（中等）
  function deleteNode(root, target){
    if (!root) return root;
    function getMin(root) {
      while(root.left) root = root.left;
      return root;
    }
    if (root.val == target){
      if (!root.left) return root.right;
      if (!root.right) return root.left;

      let minNode = getMin(root.right);
      root.val = minNode.val;
      root.right = deleteNode(root.right, minNode.val);
    } else if (root.val < target) {
      root.right = deleteNode(root.right, target);
    } else if (root.val > target) {
      root.left = deleteNode(root.left, target);
    }

    return root;
  }



  /**
   * BST框架
   *  function searchBST(root, target) {
        if(!root) return null;
        if (root.val > target) {
          return searchBST(root.left, target);
        }
        if (root.val < target) {
          return searchBST(root.right, target);
        }
        // 上面是大小情况
        // 等于的情况下，做相应处理,然后return 相应的结果
        .........

        return root;
      }
   */
}
/////////////////////////////////////////二叉树 end////////////////////////////////////////////
/////////////////////////////////////////dp start//////////////////////////////////////////
{
    /**
     *  509.斐波那契数（简单）
        322.零钱兑换（中等）
     */
    // 斐波那契数（简单）
    function fib(num) {
      let dp = Array(num);
      dp[0] = 0, dp[1] = 1;
      for(let i = 2; i <= num; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
      }
      return dp[num];
    }
    console.log(fib(20));

    // 零钱兑换
    function coinChange(coins, amount) {
      let dp = Array(amount + 1).fill(amount + 1);
      dp[0] = 0;
      for(let i = 0; i <= dp.length - 1; i++) {
        for(let v of coins) {
          if (i - v < 0 ) {
            continue;
          }
          dp[i] = Math.min(dp[i], dp[i - v] + 1);
        }
      }

      return dp[amount] == amount + 1 ? -1 : dp[amount];
    }

    console.log(coinChange([1,2,5], 11));

    // 最长递增子序列
    function lengthOfLIS(nums) {
      let dp = Array(nums.length).fill(1);

      for (let i = 0; i < nums.length; i++) {
        for(let j = 0; j < i; j++) {
          if (nums[i] > nums[j]) {
            dp[i] = Math.max(dp[i], dp[j] + 1);
          }
        }
      }

      let res = 0;
      for(let i = 0; i < dp.length; i++) {
        res = Math.max(res, dp[i]);
      }
      
      return res;
    }

    const nums = [10,9,2,5,3,7,101,18];
    console.log(lengthOfLIS(nums))

    // 背包问题
    const N = 3, // 三个物件
    W = 4, // 背包最大承载量
    wt = [2, 1, 3], // 每个物件重量
    val = [4, 2, 3]; // 每个物件价值
    
    function knapsack(w, n, wt, val) {二叉树
      let dp = Array(n + 1).fill(Array(w + 1).fill(0));
      for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= w; j++) {
          if (j - wt[i - 1] < 0) {
            dp[i][j] = dp[i - 1][j];
          } else {
            dp[i][j] = Math.max(dp[i - 1][j - wt[i - 1]] + val[i - 1], dp[i - 1][j]);
          }
        }
      }

      return dp[w];
    }

    // 背包问题，状态压缩版本
    function knapsack2(w, n, wt, val) {
      let dp = Array(w + 1). fill(0);
      for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= w; j++) {
          if (j - wt[i - 1] >= 0) {
            dp[j] = Math.max(dp[j - wt[i - 1]] + val[i - 1], dp[j]);
          }
        }
      }
      return dp[w];
    }

    console.log(knapsack2(W,N,wt,val))

    // 674. 最长连续递增序列
    const numslc = [1,3,5,4,7];
    function findLengthOfLCIS (nums) {
      let dp = Array(nums.length).fill(1);
      let res = 1;

      for (let i = 0; i < nums.length - 1; i++) {
        if (nums[i + 1] > nums[i]) {
          dp[i + 1] = dp[i] + 1;
        }
        res = Math.max(res, dp[i + 1]);
      }
      return res;
    }
    console.log(findLengthOfLCIS(numslc))
}
/////////////////////////////////////////dp end////////////////////////////////////////////
//////////////////////////////////////////////////算法 end////////////////////////////////////////////////////